\section{孙 子 定理}

\begin{frame}{物不知其所数}

我国古代《孙子算经》(南北朝， 5 世纪) 卷下第 26 题为： “今有物不知其数， 三三数之剩二， 五五数之剩三， 七七数之剩二， 问物几何?”
现被称为 “物不知其数” 问题。 
\pause
设物数为 $x$, 则问题可表述为求解
\[\tag{1}
  \begin{cases}x \equiv 2 & \left(\mod 3\right) \\ x \equiv 3 & \left(\mod 5\right) \\ x \equiv 2 & \left(\mod 7\right)\end{cases}.
\]
\pause
《孙子算经》不但给出答案 $23$, 而且还给出了算法： “凡三三数之剩一， 则置七十; 五五数之剩一， 则置二十一; 七七数之剩一， 则置十五。 一百 (零) 六以上， 以一百 (零)五减之， 即得。 
\pause
"南宋秦九韶《数书九章》给出完整系统的解答 (大衍求一术). 程大位著《算法统宗》在 1593 年更给出歌诀：
\begin{poem}
  三人同行七十稀，五树梅花廿一枝， \\
  七子团圆正半月， 除百零五便得知。 
\end{poem}
\pause
意思是， 模 $3$ 的余数 ($b_{1}=2$) 乘 $70$, 模 $5$ 的余数 ($b_{2}=3$) 乘 $21$, 模 $7$ 的余数 ($b_{3}=2$)乘 $15$, 总和除以 $105$, 余数即为答案。 
\pause
即
\begin{equation*}
  x \equiv 2 \cdot 70+3 \cdot 21+2 \cdot 15=233 \equiv 23 \quad\left(\mod 105\right). \tag{2}
\end{equation*}
\pause
$23$ 是最小正整数解， $x=23+105 k$ ($k \in \mathbb{Z})$ 都是解 (因 $105=3 \cdot 5 \cdot 7$ 除以 $3$, $5$, $7$ 的余数均为 $0$); 
\pause
反之， 若 $x$ 是解， 则 $x-23$ 被 $3,5,7$ 除的余数均为 $0$, 说明 $x-23$ 是 $105=3 \cdot 5 \cdot 7$ 的倍数， 即 $x-23=105 k, x=23+105 k$. 
\pause
故解集合恰为模 $105$ 的一个同余类。
\end{frame}

\begin{frame}
由上可见， $70$, $21$, $15$ 这三数是解决此问题的关键。 这三数何以有这等魔力呢? 
\pause
这是因为它们独特的性质：
\[
  70\equiv \begin{cases}
      1 \\ 0, \\ 0
      \end{cases}\quad 
      21\equiv \begin{cases}
        0 \\ 1, \\ 0
    \end{cases}\quad   
    15\equiv \begin{cases}
        0 \quad(\mod 3)\\ 0\quad(\mod 5); \\1\quad(\mod 7)
        \end{cases}
    \]
    \pause
    或写作
    \[
    \begin{aligned}
          70&\equiv (1,0,0)\left( \mod 3,5,7 \right),\\
          21&\equiv (0,1,0)\left( \mod 3,5,7 \right),\\
          15 & \equiv (0,0,1)\left( \mod 3,5,7 \right).
    \end{aligned}
  \]
    \pause
  此特性导致
\[
  b_{1} \cdot 70+b_{2} \cdot 21+b_{3} \cdot 15 \equiv \begin{cases}b_{1}+0+0 & \left(\mod 3\right)  \tag{4}\\ 0+b_{2}+0 & \left(\mod 5\right) \\ 0+0+b_{3} & \left(\mod 7\right)\end{cases},
\]
\pause
即
\[
  b_{1} \cdot 70+b_{2} \cdot 21+b_{3} \cdot 15\equiv (b_1,b_2,b_3)\left( \mod 3,5,7 \right).
\]
特别知 (2)式是``物不知其所数''问题的解。
\end{frame}

\begin{frame}
这种独特性质的关键数组 $70，21，15$ 是如何求得的呢? 
\pause
由于 $m_{1}=3, m_{2}=5, m_{3}=7$ 两两互素， 故 
\[
  M_{1}=m_{2} m_{3}=5 \cdot 7, \quad M_{2}=m_{1} m_{3}=3 \cdot 7, \quad M_{3}=m_{1} m_{2}=3 \cdot 5
\]
互素。 
\pause
故可通过辗转相除， 得到 Bézout 等式
\begin{equation*}
  u_{1} M_{1}+u_{2} M_{2}+u_{3} M_{3}=1 \quad\left(u_{i} \in \mathbb{Z}, \quad i=1,2,3\right). \tag{5}
\end{equation*}
\pause
由此式即可知， 
\[
  u_{1} M_{1}, \quad u_{2} M_{2}, \quad u_{3} M_{3}\quad \left(\mod 105\right)
\]
具有 $70,21,15$ 的独特性质 (3).
\pause
事实上， 对(5)式模 $m_{1}$, 则知 
\[
  u_{1} M_{1} \equiv 1\left(\mod m_{1}\right)\quad \text{(因 $m_{1}\mid M_{2}, m_{1}\mid M_{3}$)},
\]
而显然
\[
u_{1} M_{1} \equiv 0 \quad\left(\mod m_{1} \text {~或~} \mod m_{2}\right) ;
\]
同理得 $u_{2} M_{2}, u_{3} M_{3}$ 的应有性质。 实际辗转相除得到的 Bézout 等式为
\begin{equation*}
  2 \cdot(5 \cdot 7)-4 \cdot(3 \cdot 7)+1 \cdot(3 \cdot 5)=1, \tag{6}
\end{equation*}
即 
\[
  u_{1} M_{1}=70,\quad u_{2} M_{2}=-84 \equiv 21\left(\mod 105\right),\quad u_{3} M_{3}=15.
\]
\end{frame}

\begin{frame}{孙子定理}
我们事实上已经证明了：

\begin{theorem}%定理1
  [孙子定理， Chinese remainder theorem] 设整数 $m_{1}, \cdots, m_{s}$ 两两互素， 
  则对任意整数 $b_{1}, \cdots, b_{s}$, 一次同余式组 (simultaneous congruences)
\[
  \left\{\begin{array}{l}
    x \equiv b_{1} \quad\left(\mod m_{1}\right)  \tag{7}\\
  \vdots \\
x \equiv b_{s} \quad\left(\mod m_{s}\right)
\end{array}\right.
\]
总有整数解 (如$x_0$)， 且解集是 $\left\{x_{0}+m k \mid k \in \mathbb{Z}\right\}$ 
恰为模 $m=m_{1} \cdots m_{s}$ 的一个同余类。
\end{theorem}

\pause
\begin{solution*}[解法 1]  记 $M_{i}=m / m_{i}$.
  我们断言$(M_1,\cdots,M_s)=1$. 否则，
  存在素数$p$使得$p\mid M_i$, 对任意的$i$.
  故$p\mid m=\prod_i m_i$. 因此$p\mid m_i$, 对某个$i$.
  由于$m_1,\cdots,m_s$两两互素，$p\nmid m_j$, 对$j\neq i$.
  因此$p\nmid M_i=\prod_{j\neq i} m_j$, 矛盾了。
  这就证明了断言。
  进而可由辗转相除法得到 Bézout 等式
  \begin{equation*}
  u_{1} M_{1}+u_{2} M_{2}+\cdots+u_{s} M_{s}=1 \tag{8}
\end{equation*}
记 $e_{i}=u_{i} M_{i}$, 则$e_i\equiv \begin{cases}
  1 \left( \mod m_i \right),\\
  0\left( \mod m_j \right),\text{~对$j\neq i$}.
\end{cases}$
如此 $\sum_{i=1}^sb_ie_i\equiv b_j\left( \mod m_j \right)$, 对任意的$j$. 
\end{solution*}
\end{frame}
\begin{frame}
  \begin{solution*}[解法1 (续)]
    这样$x_0=\sum_{i=1}^sb_ie_i$为所给同余方程组的解。
    若$x_1$也是一个解，那么$x_1\equiv x_0\left( \mod m_i \right)$, 对任意$i$.
    由\S2.1中定理1(7)知$x_1\equiv x_0\left( \mod m \right)$.
    由此易知所给同余方程组的解为
\begin{equation*}
  x \equiv b_{1} \cdot e_{1}+b_{2} \cdot e_{2}+\cdots+b_{s} \cdot e_{s} \quad\left(\mod m\right), \tag{9}
\end{equation*}
或者说，$x=\sum_{i=1}^sb_ie_i + mk$ ($k\in \ZZ$).
  \end{solution*}

  \pause
\begin{solution*}[解法 2] 定理 1 中解法 1 可稍简化： Bézout 等式 (8) 可用同余式 (模 $m$) 代替。 
  令 $M_i=m/m_i$. 先求 $u_{i}$ 使
  \begin{equation*}
  u_{i} M_{i} \equiv 1 \quad\left(\mod m_{i}\right) \quad(1 \leqslant i \leqslant s) \tag{10}
\end{equation*}
(因 $\left(M_{i}, m_{i}\right)=1$, 故 $u_{i}$ 必存在。 可由辗转相除得 Bézout 等式 $u M_{i}+v m_{i}=1$ 得之).于是
\[
u_{1} M_{1}+u_{2} M_{2}+\cdots+u_{s} M_{s} \equiv 1 \quad(\mod m)
\]
(因此式对模 $m_{i}$ 皆成立 ($i=1, \cdots, s$), 故对模 $m$ 成立). 则令 $e_{i}=u_{i} M_{i}$ 仍可由 (9) 式求解 (因为 (9) 式是模 $m$ 同余式).
\end{solution*}


\end{frame}
\begin{frame}
例如：对 “物不知其数” 问题： $M_{1}=35, M_{2}=21, M_{3}=15$. 
\pause
求解
\[
  u_{1} 35 \equiv 1\left(\mod 3\right), \text {~即~} 2 u_{1} \equiv 1\left(\mod 3\right),
\]
易得 $u_{1}=2, e_{1}=u_{1} 35=70$. 
\pause
求解 $u_{2} 21 \equiv 1\left(\mod 5\right)$, 得 $u_{2}=1, e_{2}=21$. 
\pause
求解 $u_{3} 15 \equiv 1\left(\mod 7\right)$, 得 $u_{3}=1, e_{3}=15$.

\pause
\begin{remark}%注记1
定理 1 实质为
\[
  \left\{\begin{array}{ll}
    x \equiv 23 & \left(\mod 3\right) \\
  x \equiv 23 & \left(\mod 5\right) \\
x \equiv 23 & \left(\mod 7\right)
\end{array} \Leftrightarrow x \equiv 23 \quad\left(\mod 105\right)\right.
\]
\pause
一般情形是
\[
  \begin{cases}
      x\equiv x_0 (\mod m_1)\\
        \quad \vdots \\
          x\equiv x_0 (\mod m_s)
          \end{cases}\Leftrightarrow x\equiv x_0 (\mod m).
      \]
    其中 $m_{1}, \cdots, m_{s}$ 两两互素 (当然 $23\left(\mod 3\right)$ 即为 $2\left(\mod 3\right)$, 等等 $)$.
    从左向右看上式， 是解一次同余式组。 从右向左看， 则是一个同余式可拆为多个模互素的同余式。 这可以用来解更一般的同余式组 (各同余式的模不互素), 举例如下。
\end{remark}
\end{frame}

\begin{frame}
  \begin{example}%例1
    $\begin{cases} x \equiv 7\left(\mod 12\right) \\ x \equiv 1\left(\mod 10\right)\end{cases}$ 
    等价于 $\begin{cases} x \equiv 1\left(\mod 3\right) \\ x \equiv 3\left(\mod 4\right) \\ x \equiv 1\left(\mod 2\right) \\ x \equiv 1\left(\mod 5\right)\end{cases}$ 
    等价于 $\begin{cases} x \equiv 1\left(\mod 3\right) \\ x \equiv 3\left(\mod 4\right) \\ x \equiv 1\left(\mod 5\right)\end{cases}$
  (注意第二个方程组中第 2 式蕴涵第 3 式， 故可略去后者)。如此化为定理 1 情形。 
    此时
    \[
      m_1=3,m_2=4,m_3=5, b_1=1,b_2=3,b_3=1.
    \]
    故
    \[
      M_1=m_2m_3=20,\quad M_2=m_1m_3=15,\quad M_3=m_1m_2=12.
    \]
    接着来找$u_1,u_2,u_3$使得
    \[
      u_1M_1\equiv 1\left( \mod m_1 \right),\quad
      u_2M_2\equiv 1\left( \mod m_2 \right),\quad
      u_3M_3\equiv 1\left( \mod m_3 \right),
    \]
      或者说，
      \[
        2u_1\equiv 1\left( \mod 3\right),\quad
        -u_2\equiv 1\left( \mod 4\right),\quad
        2u_3\equiv 1\left( \mod 5\right).
      \]
      可取
        $u_1=2,  u_2=3, u_3=3.$
于是
\[
  e_1=u_1M_1=40,\quad e_2=u_2M_2=45,\quad e_3=u_3M_3=36.
\]
那么解为
   \[
     x \equiv b_1e_1+b_2e_2+b_3e_3= 211 \equiv 31\left(\mod 60\right).
   \]
\end{example}
\end{frame}

\begin{frame}
\begin{example}%例2
  $\left\{\begin{array}{l}x \equiv 7\left(\mod 12\right) \\ x \equiv 2\left(\mod 10\right)\end{array}\right.$
  等价于 $\left\{\begin{array}{l}x \equiv 1\left(\mod 3\right) \\ x \equiv 3\left(\mod 4\right) \\ x \equiv 0\left(\mod 2\right) \\ x \equiv 2\left(\mod 5\right).\end{array}\right.$
显然第 2,3 式矛盾， 原式无解。
\end{example}

\pause
\begin{example}%例3
  $\left\{\begin{array}{r@{\hspace{3pt}}l}5 x &\equiv 1\left(\mod 7\right) \\ 6 x &\equiv 10\left(\mod 8\right)\end{array}\right.$ 等价于 $\left\{\begin{array}{r@{\hspace{3pt}}l}3 \cdot 5 x &\equiv 3 \cdot 1\left(\mod 7\right) \\ 3 x &\equiv 5\left(\mod 4\right),\end{array}\right.$ 即 $\left\{\begin{array}{r@{\hspace{3pt}}l}x &\equiv 3\left(\mod 7\right) \\ x &\equiv-1\left(\mod 4\right).\end{array}\right.$
  我们有
  \[
    m_1=7, m_2=4, b_1=3,b_2=-1.
  \]
  故而
  \[
    M_1=4,\quad M_2=7.
  \]
  $M_1, M_2$的B\'ezout等式为
  \[
    2\cdot 4 +(-1)\cdot 7=1.
  \]
  这样
  \[
    e_1=8, \quad e_2=-7.
  \]
  解为$x\equiv b_1e_1+b_2e_2=31\equiv 3\left( \mod 28 \right)$.
%解得 $x=3+28 k$ ($k \in \mathbb{Z}$).
\end{example}
\end{frame}

\begin{frame}
  \begin{remark}%注记2
  可以将 (11) 式稍作演化： 对任意整数 $y$,
  \begin{equation*}
    y \equiv 0 \left(\mod m\right) \Leftrightarrow y \equiv 0 \left(\mod m_{i}\right) \quad(i=1, \cdots, s). \tag{12}
\end{equation*}
若令 $y=x-x_{0}$, 则此式即为 (11) 式。 我们也可令 $y=f(x)$ 为整系数多项式， $x$ 取整数。
\end{remark}

\pause
\begin{example}%例4
试解 (高次) 同余式： $x^{4}+12 x^{3}+13 x+4 \equiv 0 \left(\mod 15\right)$.
\pause
只需分别对模 $3$ 和模 $5$ 求解再合并，即分别求解
  $x^{4}+12 x^{3}+13 x+4 \equiv 0\left( \mod 3 \right)$和
  $x^{4}+12 x^{3}+13 x+4 \equiv 0\left( \mod 5 \right)$再合并。
模 $3$ 时，$x \equiv 0\left( \mod 3 \right)$ 非解，故由Fermat 小定理有 $x^{2} \equiv 1$, 从而模$3$的方程 相当于方程 $1+0+x+1 \equiv 0\left(\mod 3\right)$, 亦即$x \equiv 1\left(\mod 3\right)$. 
\pause
模 $5$ 时，$x\equiv 0\left( \mod5 \right)$非解，故由Fermat 小定理有 $x^{4} \equiv 1$, 从而模$5$的方程 可化为
\[
\begin{gathered}
  1+2 x^{3}-2 x-1 \equiv 0 \left(\mod 5\right)\text{~且~}x\nequiv 0\left( \mod 5 \right), \\
  x^{3} \equiv x \left(\mod 5\right)\text{~且~}x\nequiv 0\left( \mod 5 \right), \quad 
  x^{2} \equiv 1 \left(\mod 5\right).
\end{gathered}
\]
 因此 $x \equiv \pm 1\left(\mod 5\right)$. 
\pause
再由孙子定理分别解
\[
  \begin{cases}
      x\equiv 1\left(\mod 3\right)\\
        x\equiv 1\left(\mod 5\right)
        \end{cases}\quad \text{和}\quad 
        \begin{cases}
            x\equiv 1\left(\mod 3\right)\\
            x\equiv -1\left(\mod 5\right),
              \end{cases}
          \]
        得原方程解 $x=1$ 和 $4\left(\mod 15\right)$.
    \end{example}

%  \pause
% \begin{remark}%注记3
% 定理 1 对多项式也成立，即“整数”换为 “域 $F$ 上的多项式”时定理 1 仍成立。
%\end{remark}
\end{frame}

\begin{frame}{环的直和分解}


现在从另一观点看孙子定理。 注记 1 已指出， 孙子定理实质为
\[
x \equiv 23 \quad\left(\mod 105\right) \Leftrightarrow \begin{cases}x\equiv 23 \equiv 2 & \left(\mod 3\right) \\ x \equiv 23\equiv 3 & \left(\mod 5\right) \\ x \equiv 23\equiv 2 & \left(\mod 7\right)\end{cases}
\]
即： $23\left(\mod 105\right)$ 与 $(23,23,23)\equiv (2,3,2) \left(\mod 3,5,7\right)$ 双射对应。
\pause
具体对应是
\[
  23 \equiv 23 \cdot 70+23 \cdot 21+23 \cdot 15\equiv 2 \cdot 70+3 \cdot 21+2 \cdot 15\left(\mod 105\right) \mapsto(23,23,23)\equiv (2,3,2) \left(\mod 3,5,7\right).
\]
\pause
这也就是说，环 $\mathbb{Z} / 105 \mathbb{Z}$ 有 “内直和分解”：
\begin{align*}
\mathbb{Z} / 105 \mathbb{Z}&= \mathbb{Z} \overline{70} \oplus_{\mathrm{in}} \mathbb{Z} \overline{21} \oplus_{\mathrm{in}} \mathbb{Z} \overline{15} \tag{13} \\
\overline{23}&= 23 \cdot \overline{70}+23 \cdot \overline{21}+23 \cdot \overline{15} = 2 \cdot \overline{70}+3 \cdot \overline{21}+2 \cdot \overline{15}
\end{align*}
这里 $\bar{a}$ 表示 $a$ 代表的模 $105$ 同余类；
下面据上下文， $\bar{a}$ 可表示对不同模的同余类， 读者细察。
\pause
另外，$\mathbb{Z} / 105 \mathbb{Z}$的子集$\ZZ \bar{a}$作为集合由 $\bar{a}$ 的整数倍构成 ($\bar{a}$满足$\bar{a}^2=\bar{a}$时$\ZZ\bar{a}$带上$\mathbb{Z} / 105 \mathbb{Z}$中的加法和乘法构成环，这样$\ZZ\bar{a}$构成$\mathbb{Z} / 105 \mathbb{Z}$的子环)。%
\footnote{若$e$为含幺交换环$R$中幂等元 ($e$ \emph{幂等}指$e^2=e$), 
则$eR$在$R$的加法和乘法下构成幺元为$e$的含幺交换环。}
注意我们说的$R$的\emph{子环}指$R$的对加、减、乘封闭的非空子集 (此时该子环在$R$的加法和乘法下构成环)，
即使$R$是含幺环也不要求子环包含$R$的幺元 (某些地方对含幺环的子环的定义要求包含$R$的幺元)。
\end{frame}
\begin{frame}
  \begin{remark}%注记4
    (1) 设 $R_{1}, \cdots, R_{n}$ 是交换环 $R$ 的子环。 
  若任意 $r \in R$ 可写为
\[
r=r_{1}+\cdots+r_{n} \quad\left(r_{i} \in R_{i}, 1 \leqslant i \leqslant n\right),
\]
且此写法是唯一的 (或者 $0=r_{1}+\cdots+r_{n}$ 蕴涵 $r_{1}=\cdots=r_{n}=0$ ), 则称 $R$ 是 $R_{1}, \cdots$, $R_{n}$ 的 \emph{(内) 直和}， 记为
\[
R=R_{1} \oplus_{\mathrm{in}} \cdots \oplus_{\mathrm{in}} R_{n} \quad\left(\text {~符号~} \oplus_{\mathrm{in}} \text {~也常写为~} \oplus\right).
\]

\pause
(2) 设 $S_{1}, \cdots, S_{n}$ 是任意交换环 (可以有相等者), 令 $S$ 为$S_1,\cdots,S_n$的Cartesian积，即 $S=\{\left(s_{1}, \cdots, s_{n}\right)\mid s_{i} \in S_{i}, 1 \leqslant i \leqslant n\}$, 则称 $S$ 为 $S_{1}, \cdots, S_{n}$ 的 \emph{(外)直和}，%
\footnote{如此构造出的环$S$也称为$S_1,\cdots,S_n$的\emph{直积}，常记为$S_1\times \cdots \times S_n$.}
记为
 \[
 S=S_{1} \oplus_{e x} \cdots \oplus_{e x} S_{n} \quad\left(\text{符号~} \oplus_{e x} \text {~也常写为~} \oplus\right).
 \]
 \pause
 $S$ 对如下加法和乘法为环：
 \[
   \begin{gathered}
   \left(s_{1}, \cdots, s_{n}\right)+\left(s_{1}^{\prime}, \cdots, s_{n}^{\prime}\right)=\left(s_{1}+s_{1}^{\prime}, \cdots, s_{n}+s_{n}^{\prime}\right) \\
 \left(s_{1}, \cdots, s_{n}\right)\left(s_{1}^{\prime}, \cdots, s_{n}^{\prime}\right)=\left(s_{1} s_{1}^{\prime}, \cdots, s_{n} s_{n}^{\prime}\right) .
 \end{gathered}
 \]
 \pause
 $S$ 的加法单位元 (零元) 为 $(0, \cdots, 0)$, 乘法单位元 (幺元) 为 $(1, \cdots, 1)$, $\left(s_{1}, \cdots, s_{n}\right)$ 可逆当且仅当 $s_{1} \in S_{1}, \cdots, s_{n} \in S_{n}$ 分别可逆 (故$S^*=S_1^*\times \cdots \times S_n^*$)， 且逆为
 \[
   \left(s_{1}, \cdots, s_{n}\right)^{-1}=\left(s_{1}^{-1}, \cdots, s_{n}^{-1}\right).
 \]
 \end{remark}

 \end{frame}

 \begin{frame}
 注意 : $\mathbb{Z} \overline{70}=\{\overline{0}, \overline{70}, \overline{35}\}$ (因为 $3 \cdot \overline{70}=\overline{210}=\overline{0}$), 它与 $\mathbb{Z} / 3 \mathbb{Z}=\{\overline{0}, \overline{1}, \overline{2}\}$是含幺环的同构;%
 \footnote{见孙子分解定理的证明。另外，也可如下看。一般地，若$R$为含幺交换环且$e\in R$为幂等元，则容易验证有：
   (i) $R=eR\oplus_{\text{in}} (1-e)R$;
   (ii) 环同构$eR\cong R/(1-e)$
   (有满同态$R\rightarrow eR, x\mapsto ex$, 其核为$(1-e)$);
   (iii) 环同构 $R\cong R/(1-e)\oplus_{\text{ex}} R/(e)$.
   在我们这里，
   $1-\overline{70}=\overline{21+15}$, $21+15$和$105$的一个最大公因子为$3$, 因此
 \[
   (\ZZ/105\ZZ)/ (1-\overline{70})\cong \ZZ/\left( (21+15)\ZZ+105\ZZ \right)\cong \ZZ/3\ZZ.
 \]
 }
 也就是说， 如下映射 $\varphi$ 是双射 (即一一对应), 将幺元映到幺元，且保持加法和乘法 (即 $\varphi(x+y)=\varphi(x)+\varphi(y), \varphi(x y)=\varphi(x) \varphi(y)$, 对任意 $x, y \in \mathbb{Z} \overline{70}$):
 \[
   \mathbb{Z} \overline{70} \xrightarrow{\varphi} \mathbb{Z} / 3 \mathbb{Z},\quad n\cdot \overline{70}\mapsto \bar{n}~ (\overline{0} \mapsto \overline{0}, \overline{70} \mapsto \overline{1}, \overline{35} \mapsto \overline{2}).
 \]
 同理 $\mathbb{Z} \overline{21} \cong \mathbb{Z} / 5 \mathbb{Z}, \mathbb{Z} \overline{15} \cong \mathbb{Z} / 7 \mathbb{Z}$. 总之， 我们得到如下等式和环同构映射 $\sigma$ :
 \[
   \begin{aligned}
   \mathbb{Z} / 105 \mathbb{Z} & =\mathbb{Z} \overline{70} \oplus_{\mathrm{in}} \mathbb{Z} \overline{21} \oplus_{\mathrm{in}} \mathbb{Z} \overline{15} \cong \mathbb{Z} / 3 \mathbb{Z} \oplus_{e x} \mathbb{Z} / 5 \mathbb{Z} \oplus_{e x} \mathbb{Z} / 7 \mathbb{Z} \\
 & \overline{23}=2 \cdot \overline{70}+3 \cdot \overline{21}+2 \cdot \overline{15} \mapsto(\overline{2}, \overline{3}, \overline{2}) \\
 \bar{x} & =b_{1} \cdot \overline{70}+b_{2} \cdot \overline{21}+b_{3} \cdot \overline{15} \mapsto\left(\bar{b}_{1}, \bar{b}_{2}, \bar{b}_{3}\right).
 \end{aligned}
 \]
 映射 $\sigma$ 保持加法、乘法的意思是
 \[
   \begin{aligned}
   \bar{x}+\bar{x}^{\prime}&= \left(\bar{b}_{1}+\bar{b}_{1}^{\prime}, \bar{b}_{2}+\bar{b}_{2}^{\prime}, \bar{b}_{3}+\bar{b}_{3}^{\prime}\right) \\
   \bar{x} \bar{x}^{\prime}&= \left(\bar{b}_{1} \bar{b}_{1}^{\prime}, \bar{b}_{2} \bar{b}_{2}^{\prime}, \bar{b}_{3} \bar{b}_{3}^{\prime}\right).
 \end{aligned}
 \]
 我们实际上已经得到如下定理：

  \end{frame}

  \begin{frame}{孙子分解定理}

 \begin{theorem}%定理2
   [孙子分解定理] 设 $m=m_{1} \cdots m_{s}$, 而整数 $m_{1}, \cdots, m_{s}$ 两两互素，令$e_{i}$ 如定理 1所求， 则有环的直和分解和同构对应：
 \[
   \begin{aligned}
   \mathbb{Z} / m \mathbb{Z}  =\mathbb{Z} \bar{e}_{1} \oplus \cdots \oplus \mathbb{Z} \bar{e}_{s}& \stackrel{\sigma}{\cong} \mathbb{Z} / m_{1} \mathbb{Z} \oplus \cdots \oplus \mathbb{Z} / m_{s} \mathbb{Z}, \\
 %\bar{x} & =b_{1} \cdot \bar{e}_{1}+\cdots+b_{s} \cdot \bar{e}_{s} \stackrel{\sigma}{\mapsto}\left(\bar{b}_{1}, \cdots, \bar{b}_{s}\right),
   \bar{x}  =x \cdot \bar{e}_{1}+\cdots+x \cdot \bar{e}_{s} &\stackrel{\sigma}{\mapsto}\left(\bar{x}, \cdots, \bar{x}\right).
 \end{aligned}
 \]
 而且， (i) $\sigma$ 的逆映射为$(\bar{b}_1,\cdots,\bar{b}_s)\mapsto b_1\bar{e}_1+\cdots+b_s\bar{e}_s$;
 %$b_i$满足 $x \equiv b_{i}\left(\mod m_{i}\right),$
 (ii) $\mathbb{Z} \bar{e}_{i} \cong \mathbb{Z} / m_{i} \mathbb{Z}$; 
 (iii) 这些 $\bar{e}_i$ 满足
 \[
 \bar{e}_{i} \bar{e}_{j}=0 ~(\text {当~} i \neq j), \quad \bar{e}_{i}^{2}=\bar{e}_{i}, \quad\bar{e}_{1}+\cdots+\bar{e}_{s}=\overline{1} \quad(1 \leqslant i, j \leqslant s).
 \]
\end{theorem}

\pause

\begin{proof}
  我们先证明
\[
  \sigma\colon \mathbb{Z} / m \mathbb{Z}\rightarrow \mathbb{Z} / m_{1} \mathbb{Z} \oplus \cdots \oplus \mathbb{Z} / m_{s} \mathbb{Z},\quad 
  \bar{x}\mapsto \left(\bar{x}, \cdots, \bar{x}\right)
\]
为环同构。容易验证$\sigma$良定义、将幺元映到幺元、保持加法和乘法。
\pause
对任意的$(\bar{b}_1,\cdots,\bar{b}_s)\in \mathbb{Z} / m_{1} \mathbb{Z} \oplus \cdots \oplus \mathbb{Z} / m_{s} \mathbb{Z}$,
由孙子定理知存在模$m$意义下惟一的整数$x$使得$x\equiv b_i\left( \mod m_i \right)$, 对任意的$i$;
实际上，$x\equiv \sum_{i=1}^s b_i e_i\left( \mod m \right)$.
\pause
这就说明了$\sigma$是双射，且$\sigma$的逆映射$\sigma^{-1}$为$(\bar{b}_1,\cdots,\bar{b}_s)\mapsto \sum_{i=1}^s b_i \bar{e}_i$.
因此$\sigma$为环同构。（所以$\sigma$是环同构几乎就是孙子定理的重述。)
\end{proof}
  \end{frame}

  \begin{frame}
    \begin{proof}[续]
令
\[
  f_i=(0,\ldots,1,\ldots,0)\in \mathbb{Z} / m_{1} \mathbb{Z} \oplus \cdots \oplus \mathbb{Z} / m_{s} \mathbb{Z},
\]
其第$i$分量为$1$其余分量为$0$.
显然
\[
  f_if_j=0 ~(\text{对$i\neq j$}),\quad f_{i}^{2}=f_{i}, \quad f_{1}+\cdots+f_{s}=1=(\bar{1},\cdots,\bar{1}).
\]
\pause
而$\sigma^{-1}(f_i)=\bar{e}_i$且$\sigma^{-1}$保持加法、乘法并将幺元映到幺元, 我们有
 \[
   \bar{e}_{i} \bar{e}_{j}=0 ~(\text {当~} i \neq j), \quad \bar{e}_{i}^{2}=\bar{e}_{i}, \quad\bar{e}_{1}+\cdots+\bar{e}_{s}=\overline{1}.
 \]

\pause
自然地视$\ZZ/m_i\ZZ$为$\mathbb{Z} / m_{1} \mathbb{Z} \oplus \cdots \oplus \mathbb{Z} / m_{s} \mathbb{Z}$的子集，
即由非$i$分量都是$0$的那些元素构成的子集。
这个子集带上该直和中的加法、乘法构成幺元为$f_i$的环，同构于$\ZZ/m_i\ZZ$.
\pause
由于$\sigma(\bar{e}_i)=f_i$,
我们有
\[
  \sigma(\ZZ \bar{e}_i)=\ZZ f_i=\ZZ/m_i\ZZ.
\]
进而易知$\sigma$限制为同构$\ZZ \bar{e}_i \cong \ZZ/m_i\ZZ$.%
\footnote{内直和分解和外直和分解逻辑上是等价的。
  令$R$为含幺环。若$R\stackrel{\sigma}{\cong } A_1\oplus_{\text{ex}}\cdots \oplus_{\text{ex}} A_s$,
其中$A_i$为含幺环，
则$R_i=\sigma^{-1}(A_i)$在$R$的加法和乘法下构成含幺环，且$R=R_1\oplus_{\text{in}}\cdots \oplus_{\text{in}} R_s$.
反过来，
若$R=R_1\oplus_{\text{in}}\cdots \oplus_{\text{in}} R_s$,
则有环同构$R\cong R_1\oplus_{\text{ex}}\cdots \oplus_{\text{ex}} R_s$.
替换$R_i$为同构的环做外直和（直积）显然得到同构的环。
}
\pause
另外，容易通过同构$\sigma$验证
\[
  \mathbb{Z} / m \mathbb{Z} =\mathbb{Z} \bar{e}_{1} \oplus \cdots \oplus \mathbb{Z} \bar{e}_{s} .
\]
\end{proof}

%\pause
%\begin{proof}
%  第一步：$e_i$的定义性质为$e_i=u_iM_i\equiv 1\left( \mod m_i \right)$.
%  显然$e_i=u_iM_i\equiv 0\left( \mod m_j \right)$, 对$i\neq j$.
%  显然对任意的$i$, $\sum_{i=1}^s e_i\equiv 1\left( \mod m_i \right)$, 
%  故$\sum_{i=1}^s e_i\equiv 1\left( \mod m \right)$, 从而$\sum_{i=1}^s \bar{e}_i=1$.
%  对任意的$j$, 我们有$e_i^2\equiv e_i\left( \mod m_j \right)$. 
%  这样$e_i^2\equiv e_i\left( \mod m \right)$, 即$\bar{e}_i^2=\bar{e}_i$.
%  对$i\neq j$, $m\mid M_i M_j$表明$m\mid e_ie_j$, 故$\bar{e}_i \bar{e}_j=0$.
%
%  \pause
%  第二步：证明$\mathbb{Z} / m \mathbb{Z} =\mathbb{Z} \bar{e}_{1} \oplus \cdots \oplus \mathbb{Z} \bar{e}_{s}$.
%  由于$\sum_{i=1}^s\bar{e}_i=1$, 我们有$\bar{x}=x \bar{e}_1+\cdots + x \bar{e}_s$.
%  为了证明写法的唯一性，
%  设$\sum_{i=1}^s b_i\bar{e}_i=0$. 
%  那么$\sum_{i=1}^s b_ie_i\equiv 0\left( \mod m \right)$,
%  故$\sum_{i=1}^s b_ie_i\equiv 0\left( \mod m_i \right)$, 对任意的$i$.
%  由于$i\neq j$时$b_je_j\equiv 0\left( \mod m_i \right)$, 
%  我们有$b_ie_i\equiv 0\left( \mod m_i \right)$.
%  又$i\neq j$时$b_ie_i\equiv 0\left( \mod m_j \right)$, 我们有
%  $b_ie_i\equiv 0\left( \mod m \right)$, 如此，$b_i\bar{e}_i=0$. 唯一性证毕。

%第三步：证明$\ZZ \bar{e}_i\cong \ZZ/m_i\ZZ$. 
%  考虑同态
%  \[
%    \varphi\colon \ZZ/m_i\ZZ\rightarrow \ZZ \bar{e}_i,\quad \bar{a}\mapsto a \bar{e}_i. 
%  \]
%  注意到$\varphi$是良定义的：若在$\ZZ/m_i\ZZ$中$\bar{a}=\bar{b}$, 即$a\equiv b\left( \mod m_i \right)$,
%  则$u_im=m_ie_i\mid ae_i-be_i$, 故$ae_i\equiv b e_i\left( \mod m \right)$,
%  因此在$\ZZ/m\ZZ$中$a \bar{e}_i=b \bar{e}_i$.
%  又$\varphi$保持加法和乘法：
%  \[
%  \begin{aligned}
%    \varphi(\bar{a}+\bar{b}) &= \varphi(\overline{a+b})=(a+b)\bar{e}_i=a \bar{e}_i +b\bar{e}_i=  \varphi(\bar{a})+\varphi(\bar{b}),  \\
%    \varphi(\bar{a}\bar{b})&= \varphi(\overline{ab})=ab \bar{e}_i=a b\bar{e}_i^2=a\bar{e}_i\cdot b\bar{e}_i=\varphi(\bar{a})\varphi(\bar{b}).
%  \end{aligned}
%\]
%这样$\varphi$为环同构。
%
%\pause
%第四步：证明
%\[
%  \sigma\colon \mathbb{Z} / m \mathbb{Z}\rightarrow \mathbb{Z} / m_{1} \mathbb{Z} \oplus \cdots \oplus \mathbb{Z} / m_{s} \mathbb{Z},\quad 
%  \bar{x}\mapsto \left(\bar{x}, \cdots, \bar{x}\right)
%\]
%为环同构。%
%\footnote{第四步也可如下得到。若$R=R_1\oplus_{\text{in}}\cdots \oplus_{\text{in}} R_s$,
%  则有环同构$R\cong R_1\oplus_{\text{ex}}\cdots \oplus_{\text{ex}} R_s$.
%  替换$R_i$为同构的环做外直和（直积）显然得到同构的环。这样
%  \[
%    \begin{aligned}
%      \mathbb{Z} / m \mathbb{Z}&= \mathbb{Z} \bar{e}_{1} \oplus_{\text{in}} \cdots \oplus_{\text{in}} \mathbb{Z} \bar{e}_s 
%      \cong \mathbb{Z} \bar{e}_{1} \oplus_{\text{ex}} \cdots \oplus_{\text{ex}} \mathbb{Z} \bar{e}_s \\
%      &\cong  \mathbb{Z} / m_{1} \mathbb{Z} \oplus \cdots \oplus \mathbb{Z} / m_{s} \mathbb{Z}. \\
%    \end{aligned}
%\]}
%容易验证$\sigma$良定义、将幺元映到幺元、保持加法和乘法。
%对任意的$(\bar{b}_1,\cdots,\bar{b}_s)\in \mathbb{Z} / m_{1} \mathbb{Z} \oplus \cdots \oplus \mathbb{Z} / m_{s} \mathbb{Z}$,
%由孙子定理知存在模$m$意义下惟一的整数$x$使得$x\equiv b_i\left( \mod m_i \right)$, 对任意的$i$;
%实际上，$x\equiv \sum_{i=1}^s b_i e_i\left( \mod m \right)$.
%这就说明了$\sigma$是双射。因此$\sigma$为环同构。（所以$\sigma$是环同构几乎就是孙子定理换了个说法。)
%\end{proof}
\end{frame}

\begin{frame}


  \begin{corollary}%系1
    [准素分解] 若整数 $m$ 分解为素数幂之积 $m=p_{1}^{n_{1}} \cdots p_{s}^{n_{s}}$, 则
  \[
  \mathbb{Z} / m \mathbb{Z} \stackrel{\sigma}{\cong} \ZZ/ p_{1}^{n_{1}} \mathbb{Z} \oplus \cdots \oplus \mathbb{Z} / p_{s}^{n_{s}} \mathbb{Z}, \quad \bar{b} \mapsto\left(\bar{b}, \cdots, \bar{b}\right)
\]
是环的同构，
\pause
且 
$\overline{0} \mapsto(\overline{0}, \cdots, \overline{0})$, $\overline{1} \mapsto(\overline{1}, \cdots, \overline{1})$, 
$\bar{b}\in \ZZ/m\ZZ$ 可逆当且仅当所有 $\bar{b}\in \ZZ/p_i^{n_i}\ZZ$ 均可逆 ($1 \leqslant i \leqslant s$), 
且逆为 $\bar{b}^{-1}=\left(\bar{b}^{-1}, \cdots, \bar{b}^{-1}\right)$.
\pause
特别可知
\[
\varphi(m)=\varphi\left(p_{1}^{n_{1}}\right) \cdot \varphi\left(p_{2}^{n_{2}}\right) \cdots \varphi\left(p_{s}^{n_{s}}\right) \quad \text { (Euler 函数计算公式). }
\]
\pause
例如， 
\[
\begin{aligned}
  \mathbb{Z} / 6 \mathbb{Z} &\cong \mathbb{Z} / 2 \mathbb{Z} \oplus \mathbb{Z} / 3 \mathbb{Z}, \\
  \mathbb{Z} / 36 \mathbb{Z} &\cong \mathbb{Z} / 2^{2} \mathbb{Z} \oplus \mathbb{Z} / 3^{2} \mathbb{Z}.
\end{aligned}
\]
\pause
当 $m=105$ 时， $\overline{23} \mapsto (\overline{23},\overline{23},\overline{23})=(\overline{2}, \overline{3}, \overline{2})$, 故 $\overline{23}\in \mathbb{Z} / 105 \mathbb{Z}$ 可逆相当于 $\overline{2}\in \mathbb{Z} / 3 \mathbb{Z}, \overline{3}\in \mathbb{Z} / 5 \mathbb{Z}, \overline{2}\in \mathbb{Z} / 7 \mathbb{Z}$都可逆。情形确实是如此，故$\overline{23}$可逆。
\pause
实际上，
\[
  \overline{23}^{-1}\stackrel{\sigma}{=} \left(\overline{2}^{-1}, \overline{3}^{-1}, \overline{2}^{-1}\right)=(\overline{2}, \overline{2}, \overline{4})\stackrel{\sigma}{=} \overline{32},
\]
故$\overline{23}^{-1}=\overline{32}$.
\end{corollary}

\end{frame}

\begin{frame}
孙子定理和分解可以推广到主理想整环 (PID, 例如多项式环， Gauss 整数环), 无任何实质改变。 
也可推广到含幺交换环 $R$ (例如任一数域的代数整数环). 若 $m_{1},\ldots,m_s$ 为$R$的两两互素的理想 (两两互素意味着： 对$i\neq j$, $m_{i}+m_{j}=R$), 我们有同构
\[
  R /\left(m_{1} \cdots m_{s}\right) \cong R / m_{1} \oplus \cdots \oplus R / m_{s}.
\]
我们将在 \S3.1 尾部， 讨论环分解对其单位群的效果。

\pause
  \begin{comment*}%评述
  孙子定理， 古人认为很神奇， 给出许多名称： 隔墙算、鬼谷算、剪管术、大衍求一术、神奇妙算、秦王暗点兵、韩信暗点兵等。 西方直到 18 和 19 世纪才由大数学家 Euler 和 Gauss 获得。 1876 年 L. Mathiesen 指出 Gauss 的解法与《孙子算经》一致， 引起欧洲数学家的惊异和高度评价。 孙子定理至今被世界称为中国剩余定理， 是中国对世界科学的光辉贡献， 到现代有各种理论发展和应用。

孙子定理的本质， 是将数学对象分解。 现在已发展到分解各种数学系统。 “分而治之”, 是哲学智慧， 是普遍的方法论。 《孙子兵法》言：凡治众如治寡，分数是也， 就是这一思想。 又言： 夫未战而庙算胜者， 得算多也; 未战而庙算不胜者， 得算少也。 多算胜， 少算不胜， 而况无算乎! 
可见孙子特别重视“算”一一这也许是《孙子算经》托言孙子所著的原因吧。 论数者单赞这 “孙子定理之奇”曰：
\begin{poem}
隔墙不见早先知， 恑道鬼谷师孙子。\\
何须亲点百万兵， 只看游散二三士。\\
治众分数如治寡， 从此世上无巨事。\\
大衍求一真奇术， 千百年后惊高斯。
\end{poem}
\end{comment*}\end{frame}

\begin{frame}{小结}
  \begin{enumerate}
    \item 叙述孙子定理以及相关的同余方程组的求解方法。
    \item 叙述孙子分解定理、准素分解。
  \end{enumerate}
\end{frame}
